package person.bing.fbcloud.leetcode;

/**
 * 64. 最小路径和
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 *
 * @author: mengfanbing
 * @date: 2020/7/23 9:47
 */
public class Q64 {
    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int ans = minPathSum(grid);
        System.out.println(ans);
    }




    //超时
    //递归
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = minPathSumUtil(grid, m - 1, n - 1);
        return ans;
    }
    /**
     * 从左上角到grid[m][n]的最短路径
     * @param grid
     * @param m
     * @param n
     * @return
     */
    public static int minPathSumUtil(int[][] grid,int m,int n){
        int ans = grid[0][0];
        if (m == 0 && n == 0){
            return ans;
        }
        if (m == 0 && n > 0){
            for(int i=1;i<=n;i++){
                ans += grid[0][i];
            }
            return ans;
        }
        if (m > 0 && n == 0){
            for(int i=1;i<=m;i++){
                ans += grid[i][0];
            }
            return ans;
        }
        return Integer.min(minPathSumUtil(grid,m-1,n),minPathSumUtil(grid,m,n-1)) + grid[m][n];
    }
}
